package L617;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: javase
 * @description: 埃氏筛
 * @author: luolidong
 * @create: 2021-06-17 16:56
 * @version: 1.0
 */
public class Demo2 {
    public static void main(String[] args) {
        List<Integer> prime = new Demo2().getPrime(1000);
        System.out.println(prime);
    }
    public List<Integer> getPrime(int n){
        List<Integer> list=new ArrayList<>();
        boolean[] a=new boolean[n+1];
        Arrays.fill(a,true);//1.先把数组全部置为true
        for (int i = 2; i*i <=n ; i++) {
            if(a[i]==true){
//                把他的所有倍数置为false
                for (int j = i*i; j <=n ; j+=i) {
                    a[j]=false;
                }
            }
        }
        for (int i = 1; i <= n ; i++) {
           if(a[i]) list.add(i);
        }
        return list;
    }
}
